/**
 * 此文件为 ai 自动下逻辑.
 */
var overPieceList = [];     //死棋记录
var pieceTemplate = new PieceTemplate();


/**
 * ai 初始化.
 */
function aiInit() {
    overPieceList = {};
}

/**
 * ai 自动落子.
 */
function aiAutoFallPiece() {

    var validPointList = [];

    for (let i = 0; i < fallPieceStack.length; i++) {
        validPointList[validPointList.length] = fallPieceStack[i].node;
    }

    //每次循环排除一批探寻过的路径
    while (validPointList.length > 0) {
        var itemNode = null;

        if(validPointList.length === 1) {   //开局随便落子
            itemNode = getNextPoint(parseInt(Math.random()*(8-1) + 1), validPointList[0]);

        } else {
            itemNode = pathPlan(validPointList, false);
        }

        if(itemNode) {
            fallPiece(itemNode.data);
        } else {
            console.log('无地可下');
        }

        validPointList = [];     //先模拟结束
    }

    /**
     * 路径规划.
     * @param allList 全部下的棋子
     * @param piece 帮谁规划路线
     */
    function pathPlan(allList, piece) {
        var itemNode = containment(allList, !piece);       //围堵对方
        if(itemNode != null) {
            return itemNode;
        }

        itemNode = optimumPoint(allList, piece);        //找最佳落子点
        if(itemNode != null) {
            return itemNode;
        }
    }

    /**
     * 围堵对方棋子
     * @param allList   棋盘全部棋子对象
     * @param piece     围堵哪一方
     * @return object 围堵点
     */
    function containment(allList, piece) {
        //存放下一步的坐标集合，以优先级存放。 1：对方还差一步就赢的   2：交叉点局面   3. 三点一线局面    .....
        var resultMap = {};

        for (let i = 0; i < allList.length; i++) {
            var itemNode = allList[i];
            if(itemNode.data.piece !== piece) {
                continue;
            }

            //情况：对方还差一步就赢的，必须围堵
            var targetNode = pieceTemplate.preVictory(itemNode, 1, piece);
            if (targetNode != null && targetNode.length > 0) {
                recordPriority(resultMap, 1, targetNode[0]);
                continue;
            }

            //情况：探查是否有交叉点局面
            targetNode = pieceTemplate.templateGetCross(itemNode, piece);
            if(targetNode != null) {
                recordPriority(resultMap, 2, targetNode[0]);
                continue;
            }

            //情况：已有3个棋子形成一条线，需要围堵       TODO 三字没检测到的情况
            var nodeInfo = getLineContainment(itemNode, 3, piece);
            if(nodeInfo != null) {
                //反方向排查围堵
                var flag = pieceTemplate.isLineContainment(nodeInfo, getNegativeDirection(nodeInfo.direction), piece)
                if(flag) {
                    continue;    //没必要围堵
                }

                recordPriority(resultMap, 3, nodeInfo);
                continue;
            }
        }

        var resultNode = analysisPriority(resultMap);        //根据优先级返回位置
        if(resultNode) {
            return resultNode;
        }

        return null;
    }

    /**
     * 计算出最佳落子点.
     * @param allList  棋盘全部棋子对象
     * @param piece     计算哪一方的最佳落子点
     */
    function optimumPoint(allList, piece) {
        //先排除马上赢的情况
        var resultMap = {};
        for (let i = 0; i < allList.length; i++) {
            var itemNode = allList[i];
            if(itemNode.data.piece !== piece) {
                continue;
            }

            //情况：自己还差 1 步就赢的，优先下这
            var targetNode = pieceTemplate.preVictory(itemNode, 1, piece);
            if (targetNode != null && targetNode.length > 0) {
                recordPriority(resultMap, 1, targetNode[0]);
                continue;
            }

            //情况：4点一线优先下
            var nodeInfo = getLineContainment(itemNode, 4, piece);
            if(nodeInfo != null) {
                recordPriority(resultMap, 2, nodeInfo.point);
                continue;
            }

            //情况：自己还差 2 步就赢的，优先下这
            targetNode = pieceTemplate.preVictory(itemNode, 2, piece);
            if (targetNode != null && targetNode.length > 0) {
                recordPriority(resultMap, 3, targetNode[0]);
                continue;
            }

            //情况：3点一线优先下
            nodeInfo = getLineContainment(itemNode, 3, piece);
            if(nodeInfo != null) {
                recordPriority(resultMap, 4, nodeInfo);
                continue;
            }

            //情况：探查是否有交叉点局面   TODO 交叉点待补全，存在问题 ****************************
            targetNode = pieceTemplate.templateGetCross(itemNode, piece);
            if(targetNode != null) {
                recordPriority(resultMap, 5, targetNode);
                continue;
            }
        }

        var resultNode = analysisPriority(resultMap);        //根据优先级返回位置
        if(resultNode) {
            return resultNode;
        }

        //情况：没有最佳点，那就倒着开始找最后的落子点，根据这些点继续探路
        //根据空点的位置，分为三档优先级，最后取优先级最高的下
        //存放下一步的坐标集合，以优先级存放。 1：交叉点   2：直线   3.落子同时围堵    9：普普通通
        resultMap = {};
        for (let i = allList.length - 1; i >= 0; i--) {
            var currNode = allList[i];
            if(currNode != null && currNode.data.piece !== piece) {
                continue;
            }


            for (let j = 1; j <= 8; j++) {
                currNode = getNextPoint(j, allList[i]);
                if(currNode != null &&currNode.data.piece === null) {
                    //反方向排查是否存在围堵
                    var flag = pieceTemplate.isLineContainment(currNode, getNegativeDirection(j), piece)
                    if(flag) {
                        continue;    //另一头被堵上，换方向
                    }

                    //当前空点的下一步是否已经是尽头
                    var tmpNode = getNextPoint(j, currNode);
                    if(tmpNode == null || (tmpNode.data.piece !== null && tmpNode.data.piece !== piece)) {
                        continue;
                    }

                    //检查这个空点是否存在交叉的
                    tmpNode = pieceTemplate.templateGetCross(currNode, piece, 1);
                    if(tmpNode != null) {
                        recordPriority(resultMap, 1, currNode);     //交叉点优先级最高
                        continue;
                    }

                    // 当前已有2点一线，这个空点正好达到三点一线(可以创造机会)
                    tmpNode = getLineContainment(itemNode, 2, piece)
                    if(tmpNode != null) {
                        recordPriority(resultMap, 2, currNode);
                        continue;
                    }

                    //是否可以落子的同时去围堵对方
                    if(pieceTemplate.isAroundThis(itemNode, piece)) {
                        recordPriority(resultMap, 3, currNode);     //提升优先级
                        continue;
                    }

                    recordPriority(resultMap, 9, currNode); //此点位置普普通通优先级最低
                }
            }
        }

        var resultNode = analysisPriority(resultMap);        //根据优先级返回位置
        if(resultNode) {
            return resultNode;
        }

        return null;
    }

    /**
     * 记录优先级.
     * @param map   格式: {int: []}
     * @param priority  优先级
     * @param value     值
     */
    function recordPriority(map, priority, value) {
        if(map[priority]) {
            var arr = map[priority];
            arr[arr.length] = value;
        } else {
            map[priority] = [value];
        }
    }

    /**
     * 分析优先级，获取最优结果
     * @param map
     */
    function analysisPriority(map) {
        for (let i = 1; i <= 9; i++) {
            if(map[i]) {
                var arr = map[i];
                return arr[0];      //多个最优点暂时先返回第一个
            }
        }

        return null;
    }

    /**
     * 如若此点在一条线上，则返回这个线最佳的围堵落子点.
     * @param itemNode  起始点
     * @param num       几个点连城的线
     * @param piece     判断哪一方达成的
     * @return {null|*}
     */
    function getLineContainment(itemNode, num, piece) {
        var allPathList = pieceTemplate.templateGetList(itemNode, num, piece)

        if(allPathList.length > 0) {
            var allLegalPoint = [];     //全部合法节点
            var currPoint;
            for (let i = 0; i < allPathList.length; i++) {          //查看每条路径是否需要围堵
                var itemPath = allPathList[i];
                //查看此线两端是否围堵上？
                currPoint = getNextPoint(itemPath.directionNum, itemPath.pathNodeList[itemPath.startIdx]);  //获取起始节点
                if (currPoint && currPoint.data.piece === null) {
                    allLegalPoint[allLegalPoint.length] = {
                        'point' : currPoint ,
                        'direction' : itemPath.directionNum
                    };
                }
                currPoint = getNextPoint(getNegativeDirection(itemPath.directionNum), itemPath.pathNodeList[itemPath.startIdx]);  //获取结束节点
                if (currPoint && currPoint.data.piece === null) {
                    allLegalPoint[allLegalPoint.length] = {
                        'point' : currPoint ,
                        'direction' : getNegativeDirection(itemPath.directionNum)
                    };
                }
            }

            if(allLegalPoint.length === 0) {
                return null;
            }

            //根据全部路线的头部和尾部，找到最佳落子点
            for (let i = 0; i < allLegalPoint.length; i++) {
                currPoint = allLegalPoint[i].point;
                var direction = allLegalPoint[i].direction;

                //是否此点对于 piece 方可以摆阵， 或者 对于对方可以围堵
                var crossPoint = pieceTemplate.templateGetCross(currPoint, piece);
                if (crossPoint != null) {
                    return { 'point' : crossPoint, direction :  direction};         //围堵piece方
                }

                crossPoint = pieceTemplate.templateGetCross(currPoint, !piece);
                if (crossPoint != null) {
                    return { 'point' : crossPoint, direction :  direction};         //摆阵
                }

                //如果周围有自己的活棋子助阵放那
                var flag = pieceTemplate.isAroundThis(currPoint, piece);
                if(flag) {
                    return currPoint;
                }
            }

            return { 'point' : allLegalPoint[0].point, direction :  allLegalPoint[0].direction} ;
        }

        //如果都不符合围堵条件，那就不围堵
        return null;
    }

}


/**
 * 棋子模板.
 * @constructor
 */
function PieceTemplate(){
    /**
     * 返回此点所在的所有的路径.
     * @param pointNode 寻路起始点
     * @param pointCount int 需要几个点才算一条线
     * @param piece Boolean 是谁下的棋子
     * @return LinePath[] 二维数组 一维：代表路径   二维：代表每条路径中的所有点
     */
    PieceTemplate.prototype.templateGetList = function(pointNode, pointCount, piece) {
        var allPathList = [], startIdx = 0, endIdx = 0;

        //循环4个方向，另外四个反向查找
        for (let j = 1; j <= 4; j++) {
            var tmpNum = pointNode.data.piece === piece ? 1 : 0;        //给定的点是否为指定方落子
            var pathNodeList = [pointNode];

            //正向查找
            var currPoint = pointNode;
            while (currPoint = getNextPoint(j, currPoint)) {
                if(currPoint.data.piece === piece) {
                    ++tmpNum;
                    pathNodeList[pathNodeList.length]  = currPoint;
                    startIdx = pathNodeList.length - 1;
                    endIdx = pathNodeList.length - 1;
                } else {
                    break;  //对方下的棋子，无需探路，此路断
                }
            }
            //反向查找
            currPoint = pointNode;
            while (currPoint = getNextPoint(getNegativeDirection(j), currPoint)) {
                if(currPoint.data.piece === piece) {
                    ++tmpNum;
                    pathNodeList[pathNodeList.length]  = currPoint;
                    endIdx = pathNodeList.length - 1;
                } else {
                    break;  //对方下的棋子，无需探路，此路断
                }
            }

            if(tmpNum < pointCount) {
                continue;       //连不成一条线
            }

            var linePath = new LinePath(pointNode, j, pathNodeList);
            linePath.startPoint = startIdx;
            linePath.endIdx = endIdx;
            allPathList[allPathList.length] =  linePath;
        }

        return allPathList;
    }

    /**
     * 是否存在有交叉点的局面, 例如：'x、v' 字阵型.
     * 这种阵型一旦补齐交叉点就容易促成必败局面，所以需要侦察出来.
     * @param pointNode 寻路起始点
     * @param piece Boolean true:人工    false:电脑     是谁下的棋子(查看是谁满足交叉点)
     * @param num 最少几个点形成的交叉点，默认为 2
     * @return 交叉点node
     */
    PieceTemplate.prototype.templateGetCross = function(pointNode, piece, num){
        for (let j = 1; j <= 8; j++) {
            var currPoint = getNextPoint(j, pointNode);

            if(currPoint && currPoint.data.piece === null) {
                //找到此点无落子，根据此点继续探路，查看是否距离此点1格附近是否可能连接起来
                //根据 8 个方向继续探路, 查看周围是否存在连起的情况
                var count = 0;          //存在几条线
                var nullPoint = currPoint;      //记录空的交叉点

                //存在坐标并且是人工落子的时候记录
                for (let k = 1; k <= 8; k++) {
                    currPoint = nullPoint;  //掉头继续从空点的下一个方向延伸
                    var itemNum = 0;        //几个棋子连成的一条线
                    while ((currPoint = getNextPoint(k, currPoint)) && currPoint.data.piece === piece) {
                        itemNum++;
                    }

                    count += itemNum >= (num ? num : 2) ? 1 : 0;
                }

                if(count > 1) {
                    return nullPoint;         //获取交叉
                }
            }
        }

        return null;
    }

    /**
     * 预检测胜利.
     * @param pointNode 坐标节点对象
     * @param num   预检测多少步
     * @param piece 针对哪一方预检测
     * @return [] 哪些点需要围堵   如果不为null，表示再有num步就赢了，会返回围堵点
     */
    PieceTemplate.prototype.preVictory = function(pointNode, num, piece){
        for (let i = 1; i <= 4; i++) {
            var currPoint = pointNode;
            var tmpNum = pointNode.data.piece === piece ? 1 : 0;        //给定的点是否为指定方落子
            var startPoint = null, endPoint = null;       //线的起始坐标和尾部坐标

            //正向查找
            while (currPoint = getNextPoint(i, currPoint)) {
                if(currPoint.data.piece === piece) {
                    ++tmpNum;
                    startPoint = currPoint;
                } else {
                    break;  //对方下的棋子，无需探路，此路断
                }
            }
            //反向查找
            currPoint = pointNode;
            while (currPoint = getNextPoint(getNegativeDirection(i), currPoint)) {
                if(currPoint.data.piece === piece) {
                    ++tmpNum;
                    endPoint = currPoint;
                } else {
                    break;  //对方下的棋子，无需探路，此路断
                }
            }

            if(tmpNum < continuityNum - num) {
                continue;       //连不成一条线
            }

            //预先探路这条直路径，是否再走 num 步就赢？
            var justDirection = true;       //探路正反方向
            var prePath = [];
            for (let j = 0; j < num; j++) {
                currPoint = justDirection ? getNextPoint(i, startPoint) : getNextPoint(getNegativeDirection(i), endPoint);
                if(currPoint && currPoint.data.piece === null) {     //空坐标，可以落子
                    prePath[prePath.length] = currPoint;
                    if(++tmpNum === continuityNum) {     //赢了
                        return prePath;
                    }

                } else {
                    if(justDirection === false) {
                        break;
                    }
                    justDirection = false;  //掉头找
                    j--;
                }
            }
        }

        return null;
    }

    /**
     * 所在线是否另一段已被围堵.
     * 1. 当三点一线时，有一端被围堵上，则不用围堵
     * @param itemNode 空坐标 已经确定此空坐标在某条线上
     * @param directionNum 方向   会根据这个方向去推，是否这端被拦截
     * @param piece 标识自己这一方
     */
    PieceTemplate.prototype.isLineContainment = function (itemNode, directionNum, piece) {
        //根据给定方向，反推，是否反向的源头被拦截
        var currPoint = itemNode;
        while ((currPoint = getNextPoint(directionNum, currPoint))) {
            if(currPoint.data.piece === !piece) {
                return true;        //被围堵
            }

            if(currPoint.data.piece === null) {
                return false;
            }
        }

        return false;
    }

    /**
     * 是否周围有自己方的棋子.
     * @param itemNode 坐标
     * @param piece 标识自己这一方
     */
    PieceTemplate.prototype.isAroundThis = function (itemNode, piece) {
        var currPoint = null;
        for (let i = 1; i <= 8; i++) {
            currPoint = getNextPoint(i, itemNode);

            if(currPoint != null && currPoint.data.piece === piece) {
                //前提是这个点的这个方向没有被堵死
                currPoint = getNextPoint(i, currPoint);
                if(currPoint != null && (currPoint.data.piece === null || currPoint.data.piece === piece)) {
                    return true;
                }
            }

        }

        return false;
    }
}

/**
 * 返回对应方向的值.
 * @param direction 方向，值为1-8，分别为：上、右上、右、右下、下、左下、左、左上
 * @param itemNode 格子对象
 */
function getNextPoint(direction, itemNode) {
    if(itemNode === null) {
        return null;
    }

    let currNode = itemNode;
    let nextNode = null;

    switch (direction){
        case 1: nextNode = currNode.top; break;
        case 2: nextNode = currNode.top ? currNode.top.next : null; break;
        case 3: nextNode = currNode.next; break;
        case 4: nextNode = currNode.next ? currNode.next.down : null; break;
        case 5: nextNode = currNode.down; break;
        case 6: nextNode = currNode.down ? currNode.down.prev : null; break;
        case 7: nextNode = currNode.prev; break;
        case 8: nextNode = currNode.prev ? currNode.prev.top : null; break;
    }

    return nextNode;
}

/**
 * 根据方向数值，返回反方向数值.
 * @param direction
 */
function getNegativeDirection(direction){
    return direction >= 5 ? direction - 4 : direction + 4;
}

/**
 * 线阵型路径
 * @param startPoint  起始点
 * @param directionNum   方向
 * @param pathNodeList   路径
 * @constructor
 */
var LinePath = function (startPoint, directionNum, pathNodeList) {
    this.startPoint = startPoint;
    this.startIdx = 0;      //在 pathNodeList 路线数组中记录线条的起始索引
    this.endIdx = 0;        //在 pathNodeList 路线数组中记录线条的结束索引
    this.directionNum = directionNum;
    this.pathNodeList = pathNodeList;
}


















